package main

import "fmt"

//func generateParenthesis(n int) []string {
//	ans := []string{"()"}
//	var ansbing []string
//	for i := 0; i < n-1; i++ {
//		for _, v := range ans {
//			ansbing = append(ansbing, "("+v+")")
//			a, b := bing(v)
//			ansbing = append(ansbing, a)
//			if b != "" {
//				ansbing = append(ansbing, b)
//			}
//
//		}
//		ans = ansbing
//		ansbing = []string{}
//	}
//
//	return ans
//
//}
//func bing(a string) (string, string) {
//	if a == "()" {
//		return a + "()", ""
//	}
//	if a+"()" == "()"+a {
//		return a + "()", ""
//	} else {
//		return a + "()", "()" + a
//	}
//
//}

func generateParenthesis(n int) (ans []string) {
	m := n * 2
	path := make([]byte, m)
	// i=目前填了多少个括号
	// open=左括号个数，i-open=右括号个数
	var dfs func(int, int)
	dfs = func(i, open int) {
		if i == m {
			ans = append(ans, string(path))
			return
		}
		if open < n { // 可以填左括号
			path[i] = '('
			dfs(i+1, open+1)
		}
		if i-open < open { // 可以填右括号
			path[i] = ')'
			dfs(i+1, open)
		}
	}
	dfs(0, 0)
	return
}

func main() {
	fmt.Println(generateParenthesis(3))
}
